package com.lxl.todo;

import java.util.Collection;
import java.util.HashMap;
import java.util.Set;

/**
 * @Author: luoxianliang
 * @Email: 1322342586@qq.com
 * @CreateTime: 2025-08-12
 * @Description: 多数元素
 * @Version: 1.0
 * 给定一个大小为 n 的数组 nums ，
 * 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */

public class Solution25 {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = nums.length / 2;
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        Set<Integer> integers = map.keySet();
        for (Integer num : integers) {
            Integer i = map.get(num);
            System.out.println("i = " + i);
            if (i > len) {
                return num;
            }
        }
        return -1;
    }

    public int majorityElement2(int[] nums) {
       int count = 0;
       int candidate = 0;
       for (int num : nums) {
           if (count == 0) {
               candidate = num;
           }
           if (num == candidate) {
               count++;
           }
           if (num != candidate) {
               count--;
           }
       }
       return candidate;
    }

    public static void main(String[] args) {
        Solution25 solution = new Solution25();
        int[] nums = {3, 2, 3};
        System.out.println(solution.majorityElement2(nums));
    }
}
